#include <stdio.h>
#include <stdlib.h>
#include "avl.h"
#include "sqstack.h"

void InitAVLTree(AVLTree *avl)
{
        avl->root = NULL;
}

static AVLNode *GetNode(datatype *x)
{
        AVLNode *current;

        current = malloc(sizeof(AVLNode));
        current->bf = 0;
        current->data = *x;
        current->leftchild = current->rightchild = NULL;

        return current;
}

static void RotateL(AVLNode **root)
{
        AVLNode *subL, *parent;

        subL = *root;
        parent = *root = subL->rightchild;

        subL->rightchild = parent->leftchild;
        parent->leftchild = subL;

        parent->bf = subL->bf = 0;
}

static void RotateR(AVLNode **root)
{
        AVLNode *subR, *parent;
        subR = *root;
        parent = *root = subR->leftchild;

        subR->leftchild = parent->rightchild;
        parent->rightchild = subR;

        parent->bf = subR->bf = 0;
}

static void RotateRL(AVLNode **root)
{
        AVLNode *subL, *subR, *parent;

        subL = *root;
        subR = subL->rightchild;
        parent = *root = subR->leftchild;

        //将subR挂到parent的右子树上
        subR->leftchild = parent->rightchild;
        parent->rightchild = subR;
        if (parent->bf >= 0)
                subR->bf = 0;
        else
                subR->bf = 1;

        //将subL挂到parent的左子树上
        subL->rightchild = parent->leftchild;
        parent->leftchild = subL;
        if (parent->bf == 1)
                subL->bf = -1;
        else
                subL->bf = 0;

        parent->bf = 0;
}

static void RotateLR(AVLNode **root)
{
        AVLNode *subL, *subR, *parent;

        subR = *root;
        subL = subR->leftchild;
        parent = *root = subL->rightchild;

        subL->rightchild = parent->leftchild;
        parent->leftchild = subL;
        if (parent->bf <= 0) //如果(*root)有左树
                subL->bf = 0;
        else
                subL->bf = -1;

        subR->leftchild = parent->rightchild;
        parent->rightchild = subR;
        if (parent->bf == -1)
                subR->bf = 1;
        else
                subR->bf = 0;

        parent->bf = 0;
}

static void Rotate(AVLNode **node, sqstack *stack, AVLNode *current)
{
        AVLNode *parent;
        while (!stack_isempty(stack))
        {
                stack_pop(stack, &parent);
                if (parent->leftchild == current)
                        parent->bf--; //因为我们假定的平衡因子计算为(右树高度-左树高度),所以如果是在左树插入的，parent的平衡因子-1
                else                  //在右树插入的，parent的平衡因子+1
                        parent->bf++;
                if (parent->bf == 0) //平衡因子变为0，parent结点不需要调整
                        break;
                if (parent->bf == 1 || parent->bf == -1) //向上追溯结点修改平衡因子
                        current = parent;
                else // parent的平衡因子为2
                {
                        //旋转化平衡调整
                        int flag = parent->bf < 0 ? -1 : 1;
                        if (current->bf == flag) //单旋转
                        {
                                if (flag == -1)
                                        RotateR(&parent);
                                else
                                        RotateL(&parent);
                        }
                        else //双旋转
                        {
                                if (flag == 1)
                                        RotateRL(&parent);
                                else
                                        RotateLR(&parent);
                        }
                        break; //两层结点插入新结点后变为三层结点，旋转之后又变为两层，相当于没有插入结点一样，所以不需要再向上追溯结点。
                }
        }
        //旋转之后，parent指针中保存了新的根节点，但parent是临时变量，要把该值保存到以(*node)为根的树中
        if (stack_isempty(stack)) //如果栈为空就表示parent结点没有父节点，那么parnet结点就是根节点
                *node = parent;
        else //栈不为空表示parent结点还有父节点，只需从栈顶获取父节点并修改父节点的左子树或右子树
        {
                AVLNode *q;
                stack_top(stack, &q);
                if (q->data > parent->data)
                        q->leftchild = parent;
                else
                        q->rightchild = parent;
        }
}

int InsertAVLNode(AVLNode **node, datatype *x)
{
        AVLNode *current = *node, *parent = NULL;
        sqstack *stack = stack_create();

        while (current != NULL)
        {
                if (current->data == *x) //不能插入相同元素，插入失败
                        return -1;
                parent = current;
                stack_push(stack, &parent); //父节点入栈,记录插入时经过的路径
                if (current->data > *x)
                        current = current->leftchild;
                else
                        current = current->rightchild;
        }
        current = GetNode(x); //创建新节点
        if (parent == NULL)
        {
                *node = current;
                return 0;
        }
        if (parent->data > *x)
                parent->leftchild = current; //左树插入
        else
                parent->rightchild = current; //右树插入

        //修改平衡因子bf，判断是否需要旋转
        Rotate(node, stack, current);

        return 0;
}

int RemoveAVLTree(AVLNode **node, datatype *key)
{
        AVLNode *current = *node;
        AVLNode *parent = NULL;
        sqstack *stack = stack_create();

        while (current != NULL)
        {
                if (current->data == key)
                        break;
                parent = current;
                stack_push(stack, &parent);
                if (current->data > key)
                        current = current->leftchild;
                else
                        current = current->rightchild;
        }
        if (current == NULL)
                return -1;
        if (current->leftchild != NULL && current->rightchild != NULL)
        {
        }
        if (current->leftchild != NULL)
                current = current->leftchild;
        else
                current = current->rightchild;
        if (parent == NULL)
                current = parent;
        else
        {
                if (parent->leftchild == current)
                        parent->leftchild =
        }

        return 0;
}